package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.Comparator;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1036 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 很有意思的题目，虽然目前有思路，但没时间来做
     * 以后有空好好玩玩
     * @return:
     */
    class Solution {
        int EDGE = (int) 1e6, MAX = (int) 1e5;
        Set<String> set = new HashSet<>();
        int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        public boolean isEscapePossible(int[][] blocked, int[] s, int[] t) {
            for (int[] p : blocked) set.add(p[0] + "_" + p[1]);
            int n = blocked.length;
            MAX = n * (n - 1) / 2; // 字符串拼接的哈希方式常数较大，不能直接用 1e5
            return check(s, t) && check(t, s);
        }

        boolean check(int[] a, int[] b) {
            Set<String> vis = new HashSet<>();
            Deque<int[]> d = new ArrayDeque<>();
            d.addLast(a);
            vis.add(a[0] + "_" + a[1]);
            while (!d.isEmpty() && vis.size() <= MAX) {
                int[] poll = d.pollFirst();
                int x = poll[0], y = poll[1];
                if (x == b[0] && y == b[1]) return true;
                for (int[] di : dir) {
                    int nx = x + di[0], ny = y + di[1];
                    if (nx < 0 || nx >= EDGE || ny < 0 || ny >= EDGE) continue;
                    if (set.contains(nx + "_" + ny)) continue;
                    if (vis.contains(nx + "_" + ny)) continue;
                    // 该点不在障碍中 && 没有重复遍历，则加入待选集
                    d.addLast(new int[]{nx, ny});
                    vis.add(nx + "_" + ny);
                }
            }
            return vis.size() > MAX;
        }
    }


    class Solution_Need_to_be_Perfected {
        public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
            Arrays.sort(blocked, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    if (o1[0] < o2[0]) return 1;
                    else if (o1[0] == o2[0]) return o1[0] <= o2[0] ? 1 : 0;
                    else return 0;
                }
            });

            for (int[] pos : blocked) {

            }

            return true;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC1036 an = new LC1036();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
